package com.ljy.my_study.lintcode.快速排序;

import java.util.Arrays;

/**
 * @author James
 * @date 2018年10月11日
 */
public class TestMain {
	public static void main(String[] args) {
		int[] nums = { 2, 8, 4, 32, 25, 1, 6, 17, 43 };
		sort(nums, 0, nums.length - 1);
		System.out.println(Arrays.toString(nums));
	}

	public static void sort(int[] a, int low, int high) {
		int start = low;
		int end = high;
		int key = a[low];

		while (end > start) {
			// 从后往前比较
			while (end > start && a[end] >= key) // 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
				end--;
			if (a[end] <= key) {
				int temp = a[end];
				a[end] = a[start];
				a[start] = temp;
			}
			while (end > start && a[start] <= key)// 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
				start++;
			// 从前往后比较
			if (a[start] >= key) {
				int temp = a[start];
				a[start] = a[end];
				a[end] = temp;
			}
			// 此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
		}
		// 递归
		if (start > low)
			sort(a, low, start - 1);// 左边序列。第一个索引位置到关键值索引-1
		if (end < high)
			sort(a, end + 1, high);// 右边序列。从关键值索引+1到最后一个
	}
	
	public static void sort2(int[] nums,int low,int high) {
		int start=low;
		int end=high;
		int key=nums[low];
		if(start>end) {
			return;
		}
		while(start<end) {
			while(start<end&&nums[start]<=key) {
				start++;
			}
			while(start<end&&nums[end]>=key) {
				end--;
			}
			int startNum=nums[start];
			int endNum=nums[end];
			if(start<end&&nums[start]>key&&key>nums[end]) {
				int temp=nums[start];
				nums[start]=nums[end];
				nums[end]=temp;
			}
		}
		if(low<start)sort2(nums,low,start-1);
		if(end<high)sort2(nums,end+1,high);
	}

}
